This invention relates to quantum cryptography, and more particularly to apparatus and methods for encoding information in physical carriers to allow a first party to interrogate a database in possession of a second party in such a way that the first party can access only a limited part of the database, and the second party cannot discover which information was accessed.
Privacy is a major concern in many information transactions. A familiar example is provided by the transactions between web search engines and their users. In a typical transaction, a user (called “Alice” in the discussion below) accesses data held in a database controlled by a provider (called “Bob” in the discussion below). On one hand, Alice would typically prefer not to reveal to Bob the item in which she is interested (a “user privacy” problem). On the other hand, Bob owner would like not to disclose more information than that Alice has asked for (a “data privacy” problem). Typically, user privacy and data privacy are in conflict. The most straightforward way to obtain user privacy is for Alice to have Bob send her the entire database contents, leading to no data privacy whatsoever. Conversely, techniques for guaranteeing data privacy typically leave the user vulnerable (see for example, Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, Journal of Computer Systems Sciences, 60:592, 2000).
At an information theory level, this problem has been formalized by Gertner et al., as the Symmetrical Private Information Retrieval (SPIR) problem (Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Journal of Computer Systems Sciences, 60:592, 2000). This work is a generalization of the Private Information Retrieval (PIR) problem, which deals with user privacy alone. Private Information Retrieval has a large body of work devoted to it. Examples are disclosed in U.S. Pat. Nos. 5,855,018; 6,167,392; 6,438,554; 7,013,295 and 7,231,047. Other articles on the subject include “Private Retrieval of Digital Objects”, B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, Journal of the ACM, 45:965, 1998; C. Cachin, S. Micali, and M. Stadler. in Advances in Cryptology—EUROCRYPT99, 1999; C. Gentry and Z. Ramzan in Proc. 32nd ICALP, pages 803-815, 2005; S. Yekhanin, Technical Report ECCC TR06-127, 2006; E. Kushilevitz and R. Ostrovsky in Proc. 38th IEEE Symposium FOCS97, page 364, 1997).
Symmetrical Private Information Retrieval is closely related (G. Di Crescenzo, T. Malkin, and R. Ostrovsky in LNCS, 1807:122-138, 2000) to oblivious transfer. In an oblivious transfer, Bob sends to Alice N bits, out of which Alice can access exactly one bit-which one bit, Bob doesn't know (S. Wiesner, ACM SIGACT News, 15:78, 1983; M. O. Rabin. Technical Report TR-81, Harvard Aiken Computational Laboratory, 1981; A. Jakoby, M. Liskiewicz, and A. Madry, arXiv: quant-ph/0605150, 2006; G. Brassard, C. Cr'epeau, and J. M. Robert in Advances in Cryptology-Crypto86, page 234, 1987).
One problem with conventional cryptographic protocols is that they all require some assumption on the computational or technological power of eavesdropper. A sufficiently powerful eavesdropper can always intercept the information exchanged by distant parties by attacking some stage of the protocol. In any case, SPIR ensures data privacy only in the case of honest users (an honest user is defined as one who does not want to compromise her chances of getting the information about the selected item in order to get more). Quantum cryptography permits a wealth of algorithms where security is enforced by physical laws (unconditional security). No matter how powerful an eventual eavesdropper is, he cannot discover the information that the legitimate parties are exchanging. Quantum cryptographic protocols are disclosed in U.S. Pat. Nos. 5,307,410; 5,243,649; 5,850,441 and 6,678,379, 2004 and in an article entitled “Quantum key distribution method and apparatus”, C. H. Bennett and G. Brassard, Proc. IEEE Int. Conf. on Computers, Systems and Signal Processing, Bangalore, India, pages 175-179, 2003.
However, no efficient solutions in terms of both communication and computational complexity are known for SPIR (A. Ambainis in Proceedings of the 24th ICALP, Lecture Notes in Computer Science, 1256:401, 1997). Indeed, even rephrasing the known solutions at a quantum level, the best known solution for the SPIR problem (with a single database server) requires O(N) qubits to be exchanged between the server and the user, where N is the number of items contained in the database (I. Kerenidis and R. de Wolf, arXiv: quant-ph/0208062, 2002; I. Kerenidis and R. de Wolf, arXiv: quant-ph/0307076, 2003).
Slightly better performances can be obtained by assuming the existence of multiple non-mutually communicating replicas of the servers, see Refs. (B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, Journal of the ACM, 45:965, 1998; C. Cachin, S. Micali, and M. Stadler, in Advances in Cryptology-EUROCRYPT99, 1999; C. Gentry and Z. Ramzan in Proc. 32nd ICALP, pages 803-815, 2005; S. Yekhanin. Technical Report ECCC TR06-127, 2006). Moreover sub-linear communication complexity can be achieved under the some computational complexity assumption, e.g. (E. Kushilevitz and R. Ostrovsky, in Proc. 38th IEEE Symposium FOCS97, page 364, 1997). Nevertheless, no conventional single server PIR or SPIR solutions have a communication complexity or computational complexity substantially less than O(N) (B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, Journal of the ACM, 45:965, 1998; C. Cachin, S. Micali, and M. Stadler in Advances in Cryptology—EUROCRYPT99, 1999; C. Gentry and Z. Ramzan in Proc. 32nd ICALP, pages 803-815, 2005; S. Yekhanin, Technical Report ECCC TR06-127, 2006; E. Kushilevitz and R. Ostrovsky in Proc. 38th IEEE Symposium FOCS97, page 364, 1997).